package k4;

import java.util.LinkedList;
import java.util.Queue;


public class Maze {
	public Maze(){	}
	/**
	 * accessible square value
	 */
	public int visited = Integer.MAX_VALUE;
	/**
	 * inaccessible square value
	 */
	public int unvisited = Integer.MIN_VALUE;
	/**
	 * Find shortest path in maze between beginning and end square. Uses best-first search.
	 * Empty square: ' '
	 * Inaccessible square: 'X'
	 * Start square: 'B'
	 * End square: 'F'
	 * @param maze
	 * @return solved maze. Returns shortest path between start and end, path is marked with *. 
	 * Also squares that have been visited are marked with '.'.
	 */
	public char[][] solve(char[][] maze){
		Square square;
		int i, j;
		int row, column;//row and column in which we currently are
		int rowTo, columnTo;//row and column which we will go.
		int currentDistance;
		int dim = (maze.length-1)/2;
		int[][] distances = new int[2*dim+1][2*dim+1];//array holding shortest distance to each square.
		char[][] solvedMaze = new char[2*dim+1][2*dim+1];
		Queue<Square> squares = new LinkedList<Square>();//list of nodes to be processed.
		int[][] directions = {{-1,0}, {0,1}, {1,0}, {0,-1}};//four directions:
		for(i=0;i<2*dim+1;i++){
			for(j=0;j<2*dim+1;j++){
				if(maze[i][j] == 'X'){
					distances[i][j]=unvisited;
				}else if(maze[i][j] == ' '){
					distances[i][j]=visited;
				}else if(maze[i][j] == 'B'){
					distances[i][j] = 0;
					squares.add(new Square(i,j,null));
				}
				else{
					distances[i][j] = visited;
				}
				solvedMaze[i][j] = maze[i][j];//copy maze
			}
		}
		//we will process unprocessed squares one by one.
		//distance to the square is updated accordingly.
		while(true){
			square = squares.poll();
			row = square.row;
			column = square.column;
			if(maze[row][column] == 'F'){ //if solution is found
				break; 
			}
			currentDistance = distances[row][column]+1;
			solvedMaze[row][column] = '.';
			for(i=0;i<directions.length;i++){//in all four directions
				 rowTo = row + directions[i][0];
				 columnTo = column + directions[i][1];
				 if(currentDistance < distances[rowTo][columnTo]){
					 distances[rowTo][columnTo] = currentDistance;
					 squares.add(new Square(rowTo, columnTo, square));
				 }
			}
		}
		square = square.parent;
		while(square.parent != null){//fill the path with '*'
			solvedMaze[square.row][square.column]='*';
			square = square.parent;
		}
		solvedMaze[square.row][square.column] = 'B';//beginning node will be overwritten, must set it back.
		return solvedMaze;
	}
}

/**
 * Square
 * @author Kaspar
 *
 */
class Square{
	/**
	 * column where square is.
	 */
	public int column;
	/**
	 * Row where square is.
	 */
	public int row;
	public Square parent;
	public Square(int row, int column, Square parent){
		this.row = row;
		this.column = column;
		this.parent = parent;
	}
}